home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_1 / boolean < prev    next >
Internet Message Format  |  1995-03-31  |  10KB
  1. From gcw20877@uxa.cso.uiuc.edu  Tue Oct  9 20:28:07 1990
  2. Received: from bank.ecn.purdue.edu by en.ecn.purdue.edu (5.61/1.27jrs)
  3.     id AA17215; Tue, 9 Oct 90 20:28:07 -0500
  4. Received: from uxa.cso.uiuc.edu by bank.ecn.purdue.edu (5.61/1.27jrs)
  5.     id AA10740; Tue, 9 Oct 90 20:28:00 -0500
  6. Received: by uxa.cso.uiuc.edu id AA05791
  7.   (5.65+/IDA-1.3.5 for wscott@ecn.purdue.edu); Tue, 9 Oct 90 20:27:25 -0500
  8. Date: Tue, 9 Oct 90 20:27:25 -0500
  9. From: George Wang <gcw20877@uxa.cso.uiuc.edu>
  10. Message-Id: <9010100127.AA05791@uxa.cso.uiuc.edu>
  11. To: wscott@ecn.purdue.edu
  12. Status: OR
  13.  
  14. Article 3030 of comp.sys.handhelds:
  15. Path: ux1.cso.uiuc.edu!julius.cs.uiuc.edu!wuarchive!mit-eddie!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!axion!tharr!uk.ac.bristol.siva
  16. From: ARD@uk.ac.bristol.siva (Tony Duell)
  17. Newsgroups: comp.sys.handhelds
  18. Subject: HP48 & symbolic boolean algebra
  19. Keywords: HP48 boolean algebra
  20. Message-ID: <1038@tharr.UUCP>
  21. Date: 27 Sep 90 09:15:26 GMT
  22. Sender: pm111@tharr.UUCP
  23. Reply-To: Tony Duell <ARD@uk.ac.bristol.siva>
  24. Organization: Public Access to Usenet in the UK
  25. Lines: 432
  26.  
  27. A few days ago, someone (I forget who) was asking about using the HP48 for
  28. symbolic boolean algebra. Here are some routines that will do that - the
  29. best way to find out how to use them is to try them , but I will explain
  30. /give examples for any that you don't understand.
  31.  
  32. Here's an example:
  33.  
  34. {1 2 3} 2 SOP        : A AND NOT B OR NOT A AND B OR A AND B    
  35. 3 FIRST 
  36. 1 SEL 1 SEL COMM REP 
  37. 2 SEL COMM REP
  38. FCTR ON A1 REP
  39. DIST ON A1           : A OR B
  40.  
  41.     Documentation:
  42.     -------------
  43.  
  44. Here's a set of routines to do symbolic boolean algebra on the HP48SX:
  45. The file can be downloaded into your machine using kermit and contains the
  46. following operations:
  47.  
  48.     Sum of products Notation
  49.     ------------------------
  50. SOP : {n1....nn} nvars  ->  'Boolean expression'
  51.  
  52.   Generates the sum-of-products function defined by the list {n1..nn} on
  53.   nvars variables.
  54.  
  55.   e.g.
  56.   {1 2 3 4} 3 SOP gives  A AND NOT B AND NOT C OR NOT A AND B AND NOT C OR 
  57.   A AND B AND NOT C OR NOT A AND NOT B AND C
  58.  
  59. SOPTRM : nvars term -> 'boolean expression'
  60.  
  61.   Generates one SOP term 
  62.   e.g. 2 1 SOPTRM  gives A AND NOT B
  63.  
  64.  
  65.    De Morgans Laws
  66.    ---------------
  67.  
  68. DMA : 'Boolean expression' -> 'Boolean expression'
  69.  
  70.   DeMorgans law on AND 
  71.  
  72.   A AND B -> NOT( NOT A OR NOT B)
  73.  
  74. DMO : 'Boolean expression' -> 'Boolean expression'
  75.  
  76.   DeMorgans law on OR
  77.  
  78.   A OR B -> NOT (NOT A AND NOT B)
  79.  
  80.  
  81.    Simple Identities
  82.    ---------------
  83.  
  84. DBN : 'Boolean expression' -> 'Boolean expression'
  85.  
  86.   Remove DouBle Not
  87.  
  88.   NOT NOT A -> A
  89.  
  90. AN : 'Boolean expression' -> 'Boolean expression'
  91.  
  92.   A AND NOT A -> 0
  93.  
  94. ON : 'Boolean expression' -> 'Boolean expression'
  95.  
  96.   A OR NOT A -> 1
  97.  
  98. A0 : 'Boolean expression' -> 'Boolean expression'
  99.  
  100.   A AND 0 -> 0
  101.  
  102. A1 : 'Boolean expression' -> 'Boolean expression'
  103.  
  104.   A AND 1 -> A
  105.  
  106. O0 : 'Boolean expression' -> 'Boolean expression'
  107.  
  108.   A OR 0 -> A
  109.  
  110. O1 : 'Boolean expression' -> 'Boolean expression'
  111.  
  112.   A OR 1 -> 1
  113.  
  114. I0 : 'Boolean expression' -> 'Boolean expression'
  115.  
  116.   Insert 0
  117.   A -> A OR 0
  118.  
  119. I1 : 'Boolean expression' -> 'Boolean expression'
  120.  
  121.    Insert 1
  122.    A -> A AND 1
  123.  
  124.  
  125.    Distribution operators
  126.    ----------------------
  127.  
  128. DIST : 'Boolean expression' -> 'Boolean expression'
  129.  
  130.   Distribute top level function over 2nd level function (on RIGHT)
  131.   A op1 (B op2 C) -> A op1 B op2 A op1 C
  132.   where op1 and op2 are AND or OR
  133.  
  134.  
  135. DOO Distribute OR over OR
  136. DOA Distribute OR over AND
  137. DAO Distribute AND over OR
  138. DAA Distribute AND over AND
  139.   All : 'Boolean expression' -> 'Boolean expression'
  140.  
  141.   Factorisation operators - Inverses to Distribution
  142.   --------------------------------------------------
  143.  
  144. FCTR : 'Boolean expression' -> 'Boolean Expression'
  145.  
  146.   Factor 2nd level out of top level
  147.   A op1 B op2 A op1 C -> A op1 (B op2 C)
  148.  
  149. FOO, FOA, FAO, FAA exact inverses of DOO etc.
  150.  
  151.    Equation manipulation
  152.    ---------------------
  153.  
  154. SEL : 'expression' Argno -> 'Unchanged expression' Argno 'subexpression'
  155.  
  156.   Select a subexpression from the top-level function of 'expression'
  157.   Argno is 1 for the left (or only)argument, 2 for the right argument. 
  158.   The stack is left in a form suitable for manipulating 'subexpression' 
  159.   and using REP
  160.  
  161.   e.g. 'A AND (B OR C)' 2 SUB gives 'A AND (B OR C)' 2 'B OR C'
  162.  
  163. REP : 'expression' Argno 'subexpression' -> 'changed expression'
  164.  
  165.     REPlace 'subexpression' in the Argno position of the top-level function in
  166.     'expression' Use to undo SEL
  167.  
  168.     e.g. 'A AND NOT NOT B' 2 'B' REP gives 'A AND B'
  169.  
  170. (SEL can be used recursively to isolate a subexpression, and then after 
  171.  manipulating it, REP will re-assemble the expression)
  172.  
  173.  COMM : 'expression' -> 'expression' 
  174.     Commute the arguments of the top-level function in 'expression'
  175.  
  176.     e.g. 'A AND B' COMM gives 'B AND A'
  177.  
  178.  
  179.    low-level distribution/factoring routines
  180.    ----------------------------------------
  181.  
  182. DST 'expression' "OP1" "OP2" -> 'expression'
  183.    Distribute "OP1" over "OP2" in 'expression'
  184.  
  185. FCT 'expression' "OP1" "OP2" -> expression
  186.    Factor OP1 out of OP2 in expression
  187.  
  188. SETFD "OP1" "OP2" -> 'exp1' 'exp2'
  189.    Generate internal pattern-match data for DST and FCT
  190.  
  191. FIRST 'expression' n -> 'expression'
  192.    move nth term to first in expression (provided all operators above it are
  193.    of the same type)
  194.    e.g. 'A AND B AND C' 3 FIRST gives 'C AND B AND A'
  195.  
  196. NTP 'expression' -> n
  197.    Number of operators directly below or at the top level of the same 
  198.    type to top
  199.    e.g. 'A AND B AND C' NTP gives 2
  200.  
  201. M1ST 'expression' n m -> expression
  202.    Internal function used by FIRST - moves mth term in string of n to first
  203.    position
  204.  
  205. TOPFN 'expression' -> "OP"
  206.    Returns name of top-level function in expression
  207.   
  208.    e.g. 'A AND B' TOPFN gives "AND"
  209.  
  210. GEN1 "OP" n m -> 'expression'
  211.    Returns 'expression' containing n terms of form &A.... joined with operator
  212.    "OP". Terms occur in order except that mth term is swapped with the first.
  213.  
  214.    e.g. "AND" 5 3 GEN1 gives &C AND &B AND &A AND &D AND &E
  215.  
  216.  
  217. Written by A.R.Duell and placed in the public domain. This software may be
  218. freely reproduced, and published in user-group newsletters provided this 
  219. notice is retained. Further information can be obtained by contacting me
  220. at:
  221. JANET: ARD@ UK.AC.BRIS.SIVA (or BRIS.PVA if you haven't updated yet)
  222. BITNET: ARD @ SIVA.BRIS.AC.UK  
  223.  
  224. Late additions:
  225. AS: Replace A AND A with A
  226. --------------------------
  227. %%HP: T(3)A(R)F(.);
  228. \<< { '&X AND &X' &X
  229. } \|vMATCH DROP
  230. \>>
  231.  
  232. OS:Replace A OR A with A
  233. ------------------------
  234. %%HP: T(3)A(R)F(.);
  235. \<< { '&X OR &X' &X }
  236. \|vMATCH DROP
  237. \>>
  238.  
  239. 2391 bytes , checksum #677Fh
  240. ---------------->8------------->8--------->8-------------cut here------->8----
  241.  
  242. %%HP: T(3)A(R)F(.);
  243. DIR
  244.   SOP
  245.     \<< OVER SIZE \-> n
  246. m
  247.       \<< DUP 1 GET n
  248. SWAP SOPTRM SWAP 2
  249. m
  250.         FOR i i
  251. OVER SWAP GET n
  252. SWAP SOPTRM 3 ROLL SWAP
  253. OR SWAP
  254.         NEXT DROP
  255.       \>>
  256.     \>>
  257.   SOPTRM
  258.     \<< \-> n m
  259.       \<< 1 n
  260.         FOR i i 64
  261. + CHR "'" + "'"
  262. SWAP + OBJ\-> 2 i 1 -
  263. ^ R\->B m R\->B AND B\->R
  264.           IF 0 ==
  265.           THEN NOT
  266.           END
  267.           IF i 1 >
  268.           THEN AND
  269.           END
  270.         NEXT
  271.       \>>
  272.     \>>
  273.   DMA
  274.     \<< { '&X AND &Y'
  275. 'NOT(NOT &X OR NOT
  276. &Y)' } \|vMATCH DROP
  277.     \>>
  278.   DMO
  279.     \<< { '&X OR &Y'
  280. 'NOT(NOT &X AND NOT
  281. &Y)' } \|vMATCH DROP
  282.     \>>
  283.   DBN
  284.     \<< { 'NOT NOT &X
  285. ' &X } \|vMATCH DROP
  286.     \>>
  287.   AN
  288.     \<< { '&X AND NOT
  289. &X' 0 } \|vMATCH DROP
  290.     \>>
  291.   ON
  292.     \<< { '&X OR NOT
  293. &X' 1 } \|vMATCH DROP
  294.     \>>
  295.   A0
  296.     \<< { '&X AND 0'
  297. 0 } \|vMATCH DROP
  298.     \>>
  299.   A1
  300.     \<< { '&X AND 1'
  301. &X } \|vMATCH DROP
  302.     \>>
  303.   O0
  304.     \<< { '&X OR 0'
  305. &X } \|vMATCH DROP
  306.     \>>
  307.   O1
  308.     \<< { '&X OR 1' 1
  309. } \|vMATCH DROP
  310.     \>>
  311.   I0
  312.     \<< { &X '&X OR 0
  313. ' } \|vMATCH DROP
  314.     \>>
  315.   I1
  316.     \<< { &X '&X AND
  317. 1' } \|vMATCH DROP
  318.     \>>
  319.   DIST
  320.     \<< DUP TOPFN \->
  321. fn1
  322.       \<< 2 SEL TOPFN
  323. SWAP DROP fn1 SWAP
  324. DST
  325.       \>>
  326.     \>>
  327.   DOO
  328.     \<< "OR" DUP DST
  329.     \>>
  330.   DOA
  331.     \<< "OR" "AND"
  332. DST
  333.     \>>
  334.   DAO
  335.     \<< "AND" "OR"
  336. DST
  337.     \>>
  338.   DAA
  339.     \<< "AND" DUP DST
  340.     \>>
  341.   FCTR
  342.     \<< DUP TOPFN \->
  343. fn1
  344.       \<< 1 SEL TOPFN
  345. SWAP DROP fn1 FCT
  346.       \>>
  347.     \>>
  348.   FOO
  349.     \<< "OR" DUP FCT
  350.     \>>
  351.   FOA
  352.     \<< "OR" "AND"
  353. FCT
  354.     \>>
  355.   FAO
  356.     \<< "AND" "OR"
  357. FCT
  358.     \>>
  359.   FAA
  360.     \<< "AND" DUP FCT
  361.     \>>
  362.   SEL
  363.     \<< \-> n
  364.       \<< DUP OBJ\->
  365. DROP DUP
  366.         IF n <
  367.         THEN DROPN
  368.         ELSE \->LIST
  369. n GET n SWAP
  370.         END
  371.       \>>
  372.     \>>
  373.   REP
  374.     \<< \-> n trm
  375.       \<< OBJ\-> \-> tfn
  376.         \<< \->LIST n
  377. trm PUT OBJ\-> DROP
  378. tfn EVAL
  379.         \>>
  380.       \>>
  381.     \>>
  382.   COMM
  383.     \<< DUP OBJ\-> \->
  384. tfn
  385.       \<< DUP
  386.         IF 2 \=/
  387.         THEN DROPN
  388.         ELSE DROP
  389. SWAP tfn EVAL SWAP
  390. DROP
  391.         END
  392.       \>>
  393.     \>>
  394.   DST
  395.     \<< SETFD 2 \->LIST
  396. \|vMATCH DROP
  397.     \>>
  398.   FCT
  399.     \<< SETFD SWAP 2
  400. \->LIST \|vMATCH DROP
  401.     \>>
  402.   SETFD
  403.     \<< \-> fn1 fn2
  404.       \<< "'&X " fn1
  405. + "(&Y " + fn2 +
  406. " &Z)'" + OBJ\->
  407. "'(&X " fn1 +
  408. " &Y )" + fn2 +
  409. " (&X " + fn1 +
  410. " &Z)'" + OBJ\->
  411.       \>>
  412.     \>>
  413.   FIRST
  414.     \<< OVER NTP 1 +
  415. SWAP M1ST
  416.     \>>
  417.   NTP
  418.     \<< DUP DUP TOPFN
  419. 1 \-> tfn i
  420.       \<<
  421.         DO 1 SEL \->
  422. sub
  423.           \<< DROP
  424. DROP sub DUP TOPFN
  425. 'i' INCR DROP
  426.           \>>
  427.         UNTIL tfn \=/
  428.         END DROP
  429. DROP i 1 -
  430.       \>>
  431.     \>>
  432.   M1ST
  433.     \<< 3 PICK TOPFN
  434. \-> n m tfn
  435.       \<< tfn n 1
  436. GEN1 tfn n m GEN1 2
  437. \->LIST \|^MATCH DROP
  438.       \>>
  439.     \>>
  440.   TOPFN
  441.     \<<
  442.       IFERR OBJ\->
  443.       THEN DROP ""
  444.       ELSE \->STR \->
  445. tfn
  446.         \<< DROPN tfn
  447.         \>>
  448.       END
  449.     \>>
  450.   GEN1
  451.     \<< \-> m
  452.       \<< DUP
  453.         IF 1 >
  454.         THEN "&" m
  455. 64 + CHR + SWAP 2
  456. SWAP
  457.           FOR i
  458. OVER " &" + " "
  459. SWAP + +
  460.             IF i m
  461. ==
  462.             THEN
  463. "A"
  464.             ELSE i
  465. 64 + CHR
  466.             END +
  467.           NEXT SWAP
  468. DROP "'" + "'" SWAP
  469. + OBJ\->
  470.         END
  471.       \>>
  472.     \>>
  473. END
  474.  
  475.  
  476.  
  477.